/*
 * (C) 2012	Sheng Yi
 * Change an expression to postfix
 * of course, checked illegal of the expression is neccessary
 */

#include "stack.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MAXLEN	1024
#define	ISNUM(ch)	((ch >= '0' && ch <= '9') || ch == '.')
#define	ISOP(ch)	(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '%')
//#define	ISOP(ch)	(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '%' || ch == '^')

int priority[12] = {-1, 2, -1, -1, -1, -1, 2, 1, -1, 1, -1, 2};
		// 36: $ % & ' ( ) * + , - . /

int prioritycmp(char lhs, char rhs);
int check(char* src);
void expr2postfix(char* expr, char* postfix);

int main()
{
	// test for expr2postfix
	int i = 0;
	char ch;
	char expr[MAXLEN];
	while ((i < MAXLEN) && ((ch = getchar()) != '\n'))
		expr[i++] = ch;
	expr[i] = '\0';
	char postfix[MAXLEN];
	printf("expr = %s\n", expr);
	expr2postfix(expr, postfix);
	printf("postfix = %s\n", postfix);
}

int prioritycmp(char lhs, char rhs)
{
	int i = lhs - 36;
	int j = rhs - 36;
	assert(i >= 0);
	assert(j >= 0);
	i = priority[i];
	j = priority[j];
	assert(i > 0);
	assert(j > 0);
	return i - j;
}

int check(char* src)
{
	return 1;
}

void expr2postfix(char* expr, char* postfix)
{
	char ch, tmp;
	// first, check
	if (!check(expr))
		return;
	
	assert(expr != NULL);
	assert(postfix != NULL);

	while ((ch = *expr++) != '\0')
	{
		if (ch == ' ')
			continue;

		// digital and '.', copy to postfix[]
		if (ISNUM(ch))
			*postfix++ = ch;
		else if (ch == '(')
			push_c(ch);
		else if (ch == ')')	// pop untile meeting '('
		{
			while ((!empty_c()) && ((ch = pop_c()) != '('))
				*postfix++ = ch;
		}
		else if (ISOP(ch))	// operator: something like + - * / %
		{
			tmp = pop_c();
			if (tmp != '\0')
			{
				while ((tmp != '(') && (prioritycmp(ch, tmp) <= 0))
				{
					*postfix++ = tmp;
					if (!empty_c())	
						tmp = pop_c();		// becarefull overflow	
					else
					{
						tmp = '$'; // '$' is a flag, means that stack is empty
						break;
					}
				}
				if (tmp != '$')
					push_c(tmp);
			}
			push_c(ch);
		}
		else 	// others, abort. But it will amost never be excuted 
			// while we checked the expressions before
		{
			printf("Illegal symbol(s). Aborting...\n");
			exit(1);
		}
	}

	while (!empty_c())
		*postfix++ = pop_c();

	*postfix = '\0';	// end of string
}
